/*
题目: 不同的子序列Ⅱ
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

    例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

https://leetcode.cn/problems/distinct-subsequences-ii
 */
public class DistinctSubseqⅡ {
    private static final int MOD = (int) 1e9 + 7;
    public int distinctSubseqII(String s) {
        int n = s.length();
        // 以 某个字母 结尾的子序列个数
        int[] cnt = new int[26];

        // 任何一个字母的更新 -- 等于前面每个字母结尾的子序列的个数之和 再 加上自己单独的一个字母 (也就是 + 1)
        for (int i = 0; i < n; i ++) {
            int pos = s.charAt(i) - 'a';
            int total = 1; // 包括自己单独的一个字母
            for (int j = 0; j < 26; j ++)
                total = (total + cnt[j]) % MOD;

            cnt[pos] = total % MOD;
        }

        // 加上所以字母结尾的子序列, 这包括所有 [单独字母] 的子序列
        int src = 0;
        for (int i = 0; i < 26; i ++) {
            src = (src + cnt[i]) % MOD;
        }
        return src;
    }
}
